package dp;

public class Rob {
    //打家劫舍问题  给定一组数组 表示每家的价值  不能偷相邻的两家  求可以偷的最大价值
    public static void main(String[] args) {
        int[] arr ={1,2,3,1};
        int[] arr2 = {2,7,9,3,1};
        System.out.println(getMaxSumWithDP(arr));
        System.out.println(getMaxSumWithDP(arr2));
    }

    //递归
    public static int getMaxSum(int[] arr,int index){
        if (index >=arr.length){
            return 0;
        }
        int res1 = arr[index] + getMaxSum(arr,index+2);
        int res2 = getMaxSum(arr,index+1);
        return Math.max(res1,res2);
    }

    //动态规划
    public static int getMaxSumWithDP(int[] arr){
        int[] dp = new int[arr.length+2];
        dp[arr.length] = 0;
        dp[arr.length+1] = 0;
        for (int a=arr.length-1;a>=0;a--){
            dp[a] = Math.max(arr[a] + dp[a+2],dp[a+1]);
        }
        return dp[0];
    }
}
